// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#ifndef MGCTHEAP_H
#define MGCTHEAP_H

#include "MgcTArray.h"

// Implementation of a maximum heap.  Viewed as a binary tree, each node's
// key is greater than or equal to its children's keys.  The class T is
// intended to be native data.

template <class T>
class MgcTHeap
{
public:
    // Construction and destruction.  If uiQuantity is zero, elements can be
    // added using Add().  The heap is then constructed using Build().  If
    // uiQuantity > 0, then operator[] must be used to initialize the
    // elements, not Add().
    MgcTHeap (unsigned int uiQuantity, unsigned int uiGrowBy = 1);

    // element access
    unsigned int GetQuantity () const;
    T& operator[] (unsigned int uiIndex) const;

    // heap operations
    void Add (T tRecord);
    void Remove (T& rtMaximum);

    // reorganize records to form a heap
    void Build ();

    // sort records, smallest to largest
    void Sort ();

    // for debugging purposes
    bool IsValid ();

protected:
    // for debugging purposes
    bool IsValid (int iStart, int iFinal);

    unsigned int m_uiQuantity, m_uiGrowBy;
    MgcTArray<T> m_tArray;
};

#include "MgcTHeap.inl"

#endif
